//===----------------------------------------------------------------------===//
//
//                         BusTub
//
// lru_k_replacer.cpp
//
// Identification: src/buffer/lru_k_replacer.cpp
//
// Copyright (c) 2015-2022, Carnegie Mellon University Database Group
//
//===----------------------------------------------------------------------===//

#include "buffer/lru_k_replacer.h"
#include "common/exception.h"

namespace bustub {

LRUKReplacer::LRUKReplacer(size_t num_frames, size_t k) : replacer_size_(num_frames), k_(k) {}

LRUKNode::LRUKNode(frame_id_t fid, size_t k) : k_(k), fid_(fid) {}

auto LRUKNode::GetIsEvictable() const -> bool { return is_evictable_; }

auto LRUKNode::SetIsEvictable(bool evictable) -> void { is_evictable_ = evictable; }

auto LRUKNode::Getk_() const -> size_t { return k_; }

auto LRUKNode::Setk_(size_t k) -> void { k_ = k; }

auto LRUKNode::Gethistory_() const -> const std::list<Access> & { return history_; }

auto LRUKNode::Getfid_() const -> frame_id_t { return fid_; }

auto LRUKNode::Setfid_(frame_id_t fid) -> void { fid_ = fid; }

auto LRUKNode::ClearHistory() -> void { history_.clear(); }

auto LRUKNode::RecordAccess(size_t current_timestamp, AccessType access_type) -> void {
  Setk_(Getk_() + 1);
  history_.push_back({current_timestamp, access_type});
}

auto LRUKNode::GetLatestTimestamp() const -> size_t { return history_.back().timestamp; }

auto LRUKNode::GetEarliestTimestamp() const -> size_t { return history_.front().timestamp; }

auto LRUKReplacer::GetTimeBetween(LRUKNode lruknode) const -> size_t {
  return current_timestamp_ - lruknode.GetLatestTimestamp();
}

/**
 * 驱逐一个可驱逐的页面，把驱逐的页面id存在frame_id中
 * 1. 如果可驱逐的页面数量为0，直接返回false
 * 2. 先去不在缓冲区的页面(history_list_)中找
 * 3. 如果不在缓冲区的页面中没有可驱逐的，就去在缓存去的页面中找
 * 4. 如果都没有找到，就返回false
 */
auto LRUKReplacer::Evict(frame_id_t *frame_id) -> bool {
  std::scoped_lock<std::mutex> lock(latch_);
  if (curr_size_ == 0) {
    return false;
  }
  std::shared_ptr<LRUKNode> earliest_node = nullptr;
  // 先去historylist里找
  // 设置一个最小的时间，寻找每个页面离现在时间间隔的最大值，就是要放逐的页面
  size_t earliest_timestamp = std::numeric_limits<size_t>::max();
  for (auto it = history_list_.begin(); it != history_list_.end(); it++) {
    if (!it->second->GetIsEvictable()) {
      continue;
    }
    if ((*it->second).GetEarliestTimestamp() < earliest_timestamp) {
      earliest_timestamp = (*it->second).GetEarliestTimestamp();
      *frame_id = it->second->Getfid_();
      earliest_node = it->second;
    }
  }
  if (earliest_node != nullptr) {
    history_list_.erase(*frame_id);
    earliest_node->SetIsEvictable(false);
    earliest_node->Setk_(0);
    curr_size_--;
    return true;
  }

  // 再去bufferedlist里找
  size_t earliest_time = std::numeric_limits<size_t>::min();
  for (auto it = buffered_list_.begin(); it != buffered_list_.end(); it++) {
    if (!it->second->GetIsEvictable()) {
      continue;
    }
    if (GetTimeBetween(*it->second) > earliest_time) {
      earliest_time = GetTimeBetween(*it->second);
      *frame_id = it->second->Getfid_();
      earliest_node = it->second;
    }
  }
  if (earliest_node != nullptr) {
    buffered_list_.erase(*frame_id);
    earliest_node->SetIsEvictable(false);
    earliest_node->Setk_(0);
    curr_size_--;
    return true;
  }
  return false;
}

// 在RecordAccess方法中使用std::shared_ptr
void LRUKReplacer::RecordAccess(frame_id_t frame_id, AccessType access_type) {
  std::scoped_lock<std::mutex> lock(latch_);
  if (frame_id > static_cast<int>(replacer_size_)) {
    throw Exception("The frame_id is out of range");
  }
  // 如果frame_id不在node_store_中，创建一个新的LRUKNode并插入
  if (node_store_.find(frame_id) == node_store_.end()) {
    auto page = std::make_shared<LRUKNode>(frame_id, 0);
    page->Setfid_(frame_id);
    node_store_.insert({frame_id, page});
    history_list_.insert({frame_id, page});
  }
  auto frame = node_store_.find(frame_id);
  auto page = frame->second;
  page->RecordAccess(current_timestamp_, access_type);

  // 如果这个页面经过这次record访问次数达到了k，就把它从historylist中取出，放到bufferedlist中
  if (page->Getk_() >= k_) {
    // 该页面依旧在historylist中存在（之前没有被evict）
    if (history_list_.find(frame_id) != history_list_.end()) {
      history_list_.erase(frame_id);
      buffered_list_.insert({frame_id, page});
    } else {
      buffered_list_.insert({frame_id, page});
    }
  } else {
    if (history_list_.find(frame_id) == history_list_.end()) {
      history_list_.insert({frame_id, page});
      page->Setk_(page->Getk_() + 1);
    }
  }
  current_timestamp_++;
}

/**
 * 如果一个页是可驱逐的，要被设置成不可驱逐的，说明可驱逐的页面数量-1，curr_size_--
 * 如果一个页是不可驱逐的，要被设置成可驱逐的，说明可驱逐的页面数量+1，curr_size_++
 */
void LRUKReplacer::SetEvictable(frame_id_t frame_id, bool set_evictable) {
  std::scoped_lock<std::mutex> lock(latch_);
  auto frame = node_store_.find(frame_id);
  if (frame == node_store_.end()) {
    return;
  }
  if (frame->second->GetIsEvictable() && !set_evictable) {
    frame->second->SetIsEvictable(false);
    curr_size_--;
  } else if (!frame->second->GetIsEvictable() && set_evictable) {
    frame->second->SetIsEvictable(true);
    curr_size_++;
  }
}

void LRUKReplacer::Remove(frame_id_t frame_id) {
  std::scoped_lock<std::mutex> lock(latch_);
  auto frame = node_store_.find(frame_id);
  if (frame == node_store_.end()) {
    return;
  }
  if (!frame->second->GetIsEvictable()) {
    throw Exception("The frame is not evictable");
  }
  auto page = frame->second;
  if (page->Getk_() < k_) {
    history_list_.erase(frame_id);
  } else if (page->Getk_() == k_) {
    buffered_list_.erase(frame_id);
  }
  curr_size_--;
  node_store_.erase(frame_id);
  page->SetIsEvictable(false);
  page->Setk_(0);
}

auto LRUKReplacer::Size() -> size_t { return curr_size_; }

}  // namespace bustub
